package com.jxb.five;

/**
 * 最小覆盖子串
 *
 * @author jiaobo
 * @date Created in 2025/1/3 22:09
 **/
public class MinWindowSubstring_76 {

    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t== null || t.length() == 0) {
            return "";
        }

        int[] tChars = new int[128];
        for (int i = 0;i<t.length();i++) {
            tChars[t.charAt(i)]++;
        }

        int left = 0,right = 0;
        int size = Integer.MAX_VALUE,count = t.length();
        int start = 0;
        //遍历所有的字符
        while (right < s.length()) {
            char c = s.charAt(right);
            if (tChars[c] > 0) {
                count--;
            }
            tChars[c]--;
            if (count == 0) {
                while (left <right && tChars[s.charAt(left)] < 0) {
                    tChars[s.charAt(left)] ++;
                    left++;
                }
                if (right - left + 1 < size) {
                    size = right - left + 1;
                    start = left;
                }
                tChars[s.charAt(left)]++;
                left++;
                count++;
            }
            right++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start,start+size);
    }

}
